package com.leetcode;

/**
 * 二叉树展开为链表
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * <p>
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 */
public class No114 {
    public void flatten(TreeNode root) {
        if (root == null) return;
        dfs(root);
    }

    public TreeNode dfs(TreeNode root) {
        if (root == null) return null;
        TreeNode left = root.left;
        TreeNode right = root.right;
        TreeNode tail = root;
        tail.left = null;
        if (left != null) {
            TreeNode leftTail = dfs(left);
            tail.right = left;
            tail = leftTail;
        }
        if (right != null) {
            TreeNode rightTail = dfs(right);
            tail.right = right;
            tail = rightTail;
        }
        return tail;
    }


    public void flatten2(TreeNode root) {
        if (root == null) return;
        flatten2(root.left);
        flatten2(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        while (root.right != null) {
            root = root.right;
        }
        root.right = temp;
    }
}
